A version control system tracks changes made to a repository of files over time. The repository of files may be associated with a project having multiple files that may be accessed by different users independently. The version control system tracks changes made to a repository of files in the project in order to provide the ability to revert back to a prior version of a file or to ascertain information pertaining to the changes made to the repository.
A version control system is useful in software development projects that have several developers collaborating in the development independently and in different geographic locations. A repository of files may be distributed to multiple developers who edit the files independently. The version control system provides a mechanism to track the changes made to the files in the repository over time, the ownership of the changes, and the history of all the changes made.
Version control systems may use directed acyclic graphs (DAGs) to track the different versions of the repository and information pertaining to the changes made with each version. A DAG has an inherent hierarchical ordering which is similar to the hierarchical structure of a file system. This makes the DAG a natural choice for representing the repository. Queries relating to the version history of a repository use tree traversal techniques to traverse the DAG to obtain the data needed to formulate a response to the query. However, a DAG representing a large repository may contain a large number of nodes thereby consuming a considerable amount of computing time to traverse the DAG to obtain the information needed to answer the query.